/*
    DIMVisual, the Data Integration Model for Visualization of trace files.
    Copyright (c) 2008 Lucas Mello Schnorr <schnorr@gmail.com>

    This file is part of DIMVisual.

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#include "BinaryMinHeap.h"

@implementation BinaryMinHeap
- (id) init
{
	self = [super init];
	sources = [[NSMutableArray alloc] init];
	lastRemoved = nil;
	return self;
}

- (void) dealloc
{
	[sources release];
	[super dealloc];
}

- (void) orderToTopIndex: (int) i
{
	if (i == 0){
		return;
	}
	int iparent = (int)((i-1)/2);
	id index, parent;
	index = [sources objectAtIndex: i];
	parent = [sources objectAtIndex: iparent];
	if ([index compareTime: parent] == NSOrderedAscending){
		[sources exchangeObjectAtIndex: i
			     withObjectAtIndex: iparent];
		[self orderToTopIndex: iparent]; 
	}
}

- (void) orderToBottomIndex: (int) i
{
	int max = [sources count];
	if (i == max){
		return;
	}

	int ichild1 = 2*i + 1;
	int ichild2 = 2*i + 2;

	id index = [sources objectAtIndex: i];
	id child1 = nil, child2 = nil;
	if (ichild1 < max){
		child1 = [sources objectAtIndex: ichild1];
	}
	if (ichild2 < max){
		child2 = [sources objectAtIndex: ichild2];
	}

	/* choose child */
	id target = nil;
	int itarget;
	if (!child1){
		target = child2;
		itarget = ichild2;
	}else if (!child2){
		target = child1;
		itarget = ichild1;
	}else if (child1 && child2){
		if ([child1 compareTime: child2] == NSOrderedDescending){
			target = child2;
			itarget = ichild2;
		}else{
			target = child1;
			itarget = ichild1;
		}
	}
	if (target && [index compareTime: target] == NSOrderedDescending){
		[sources exchangeObjectAtIndex: i
			     withObjectAtIndex: itarget];
		[self orderToBottomIndex: itarget];
	}
}

- (id<FileReader>) remove
{
	id<FileReader,NSObject> ret;
	ret = [sources objectAtIndex: 0];
	if (ret == nil){
		return nil;
	}
	[ret retain];
	if ([sources count] > 1){
		[sources exchangeObjectAtIndex: 0
			     withObjectAtIndex: [sources count] - 1];
	}
	[sources removeObjectAtIndex: [sources count] - 1];
	[self orderToBottomIndex: 0];
	[ret autorelease];
	return ret;
}

- (void) add: (id<Time>) source
{
	[sources addObject: source];
	[self orderToTopIndex: [sources count] - 1];
}


- (id<Time>) mostRecent
{
	id ret;

	if (lastRemoved && [lastRemoved time] != nil){
		[self add: lastRemoved];
		[lastRemoved release];
		lastRemoved = nil;
	}

	while ([sources count] > 0){
		lastRemoved = [self remove];
		[lastRemoved retain];
		if ([lastRemoved time] == nil){
			[lastRemoved autorelease];
			ret = lastRemoved;
			lastRemoved = nil;
		}else{
			ret = lastRemoved;
		}
		return ret; 
	}
	return nil;
}
@end
